package 中等.图;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.PriorityQueue;

/**
 * 有 n 个网络节点，标记为 1 到 n。
 * 给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，
 * 其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
 * 现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使
 * 所有节点收到信号，返回 -1 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/network-delay-time
 */
public class 网络延迟时间_743 {

    public static void main(String[] args) {

        System.out.println(networkDelayTime(new int[][]{
                        {1, 3, 10},
                        {1, 6, 100},
                        {1, 5, 30},
                        {2, 3, 5},
                        {3, 4, 50},
                        {4, 6, 10},
                        {5, 4, 20},
                        {5, 6, 60},
                },
                6, 1));

    }

    /**
     * 单源最短路径算法 Dijkstra+最小堆
     * 将所有节点分成两类：已确定从起点到当前点的最短路长度的节点，以及未确定从起点到当前点的
     * 最短路长度的节点（下面简称「未确定节点」和「已确定节点」）。
     * 每次从「未确定节点」中取一个与起点距离最短的点，将它归类为「已确定节点」，并用它「更新」
     * 从起点到其他所有「未确定节点」的距离。直到所有点都被归类为「已确定节点」。
     * 用节点 A「更新」节点 B 的意思是，用起点到节点 A 的最短路长度加上从节点 A 到节点 B 的边的
     * 长度，去比较起点到节点 B 的最短路长度，如果前者小于后者，就用前者更新后者。这种操作也被
     * 叫做「松弛」。
     * 可以这样理解，因为我们已经用了每一个「已确定节点」更新过了当前节点，无需再次更新（因为一
     * 个点不能多次到达）。而当前节点已经是所有「未确定节点」中与起点距离最短的点，不可能被其
     * 它「未确定节点」更新。所以当前节点可以被归类为「已确定节点」。
     * 注意：每次选择「未确定节点」时，起点到它的最短路径的长度可以被确定，而不是
     * 每次选择「未确定节点」相邻的节点都会被确定，只有每次选择的未确定节点中的和起点最近的节点
     * 被确定！！！
     */
    public static int networkDelayTime(int[][] times, int n, int k) {
        // 用来保存源点到给个节点的最短距离
        int[] dis = new int[n + 1];
        // 存在环，访问过确定的节点不再访问
        boolean[] visited = new boolean[n + 1];
        // 需要在已确定节点的集合，找到和源点距离最小的且没有找过的节点
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((a, b) -> dis[a] - dis[b]);
        // 需要快速找到，某个节点相邻的其余节点集合
        List<int[]>[] nextTimes = new List[n + 1];
        for (int[] time : times) {
            List<int[]> nextTime = nextTimes[time[0]];
            if (nextTime == null) {
                nextTime = new ArrayList<>();
                nextTimes[time[0]] = nextTime;
            }
            nextTime.add(new int[]{time[1], time[2]});
        }

        // 初始化
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[k] = 0;
        priorityQueue.add(k);

        while (!priorityQueue.isEmpty()) {
            int curTime = priorityQueue.poll();
            // 只有从堆顶取出来的节点，才是已经确认该节点到起点的最短距离
            if (visited[curTime]) continue;
            visited[curTime] = true;

            List<int[]> nextTime = nextTimes[curTime];
            if (nextTime != null) {
                for (int[] next : nextTime) {
                    if ((dis[curTime] + next[1]) < dis[next[0]]) {
                        dis[next[0]] = dis[curTime] + next[1];
                        priorityQueue.add(next[0]);
                    }
                }
            }
        }
        int maxDis = 0;
        for (int i = 1; i < dis.length; i++) {
            if (dis[i] == Integer.MAX_VALUE) {
                return -1;
            }
            maxDis = Math.max(maxDis, dis[i]);
        }
        return maxDis;
    }

}
